import random
import networkx as nx
import matplotlib.pyplot as plt

def Cartesianproduct(X, Y):     #生成边
    XY = set({})
    for x in X:
        for y in Y:
            XY.add((x, y))
    return XY

def creategraph(m, n):          #随机生成图
    global V, XY
    V = range(m)
    XY = Cartesianproduct(V, V)
    E = random.sample(XY, n)
    return [V, E]

def Cartesianproductweight(X, Y):   #生成有向边
    XY = set({})
    for x in X:
        for y in Y:
            weight  = random.randint(1, 100)
            XY.add((x, y, weight))
    return XY

def weightedgraph(V0, E0, W0):  #生成权图
    V = V0
    E = set({})
    for (u, v) in E0:
        w = random.randint(1, W0)
        E = E | {(u, v, w)}
    return [V, E]


def drawgraph(E):               #画图
    G = nx.Graph()
    G.add_edges_from(E)
    nx.draw(G, node_size=200, node_color='r', with_labels=True, font_color='w')
    plt.show()
    return

def drawweightgraph(E):         #画权图
    G = nx.Graph()
    G.add_weighted_edges_from(E)
    nx.draw(G, node_size=200, node_color='r', with_labels=True, font_color='w')
    plt.show()
    return

def drawdigraph(E):             #画有向图
    G = nx.DiGraph()
    G.add_edges_from(E)
    nx.draw(G, node_size=200, node_color='r', with_labels=True, font_color='w')
    plt.show()
    return

def isgraph(V, E):              #判断是否为图
    tv = True
    for (u, v) in E:
        tv = tv and (u in V) and (v in V)
    return tv

def issubgraph(V, E, Vs, Es):   #判断是否为子图
    tv = (Vs <= V) and (Es <= E)
    return tv

def ispropersubgraph(V, E, Vs, Es): #判断是否为真子图
    tv = ((Vs <= V) and (Es <= E)) and ((Vs < V) or (Es < E))
    return tv

def isspanningsubgraph(V, E, Vs, Es):   #判断是否为生成子图
    tv = ((Vs <= V) and (Es <= E)) and ((Vs == V) and (Es <= E))
    return tv

def isinducedsubgraph(V, E, Vs, Es):    #判断是否为导出子图
    tv = (Vs <= V) and (Es <= E)
    for (u, v) in E:
        tv = tv and ((not((u in Vs) and (v in Vs))) or ((u, v) in Es))
    return tv

def degreeset(V, E):        #计算图的出入度
    V = sorted(V)
    m = len(V)
    di = [0] * m
    do = [0] * m
    d = [0] * m
    for (u, v) in E:
        i = V.index(u)
        j = V.index(v)
        di[j] += 1
        do[i] += 1
        d[i] += 1
        d[j] += 1
    return [d, di, do]

def degreesetw(V, E):
    V = sorted(V)
    m = len(V)
    di = [0] * m
    do = [0] * m
    d = [0] * m
    for (w, u, v) in E:
        i = V.index(u)
        j = V.index(v)
        di[j] += 1
        do[i] += 1
        d[i] += 1
        d[j] += 1
    return [d, di, do]

def completegraphset(n):        #生成完全图
    V = set({})
    E = set({})
    for i in range(n):
        V = V | {i}
        for j in range(n):
            E = E | {(i, j)}
    return (V, E)

def completegraphlist(n):       #生成完全图列表
    V = set({})
    E = []
    for i in range(n):
        V = V | {i}
        for j in range(n):
            E = E + [[i, j]]
    return [V, E]

def cyclicgraphset(n):      #生成圈图
    V = {0}
    E = set({})
    for k in range(1, n):
        V = V | {k}
        E = E | {(k - 1, k)}
    E = E | {(n - 1, 0)}
    return (V, E)

def cyclicgraphlist(n):     #生成圈图列表
    V = {0}
    E = []
    for k in range(1, n):
        V = V | {k}
        E = E + [[k - 1, [k]]]
    E=E +[[n - 1, [0]]]
    return (V, E)

def wheelggraphset(n):      #生成轮图
    V = {0, 1}
    E = set({})
    for k in range(1, n):
        V = V | {k}
        E = E | {(0, k)}
        E = E | {(k - 1, k)}
    E = E | {(n - 1, 1)}
    return (V, E)

def wheelggraphlist(n):     #生成轮图列表
    V = {0, 1}
    E = []
    E0 = []
    for k in range(1, n):
        V = V | {k}
        E0 = E0 + [k]
        E = E + [[k - 1, [k]]]
    E = E + [[n - 1,[1]]] + [[0, E0]]
    e = [0, [1]]
    E.remove(e)
    return (V, E)

def ncubegraphset(m):       #生成n立方体图
    V = set({})
    E = set({})
    n = 2 ** m
    for i in range(n):
        V = V | {i}
        u = 1
        k = 0
        while (k < m):
            if (i & u == 0):
                j = i | u
            else:
                j = i - u
            E = E | {(i, j)}
            u = u * 2
            k = k + 1
    return (V, E)

def ncubegraphlist(m):      #生成n立方体图列表
    V = set({})
    E = []
    n = 2 ** m
    for i in range(n):
        V = V | {i}
        u = 1
        k = 0
        E0 = []
        while (k < m):
            if (i & u == 0):
                j = i | u
            else:
                j = i - u
            E0 = E0 + [j]
            u = u * 2
            k = k + 1
        E = E + [[i, E0]]
    return (V, E)

def sequence01graphset(m):      #生成0-1序列图
    V = set({})
    E = set({})
    n = 2 ** m
    for i in range(n):
        V = V | {i}
        j = (2 * i) % n
        E = E | {(i, j)}
        j = (2 * i + 1) % n
        E = E | {(i, j)}
    return (V, E)

def sequence01graphlist(m):     #生成0-1序列图列表
    V = set({})
    E = []
    n = 2 ** m
    for i in range(n):
        V = V | {i}
        j0 = (2 * i) % n
        j1 = (2 * i + 1) % n
        E = E + [[i, [j0, j1]]]
    return (V, E)

def completebigraphset(m,n):    #生成完全偶图
    Vx = set(range(m))
    Vy = set(range(n))
    V0 = set({})
    V1 = set({})
    E = set({})
    for u in Vx:
        for v in Vy:
            x = 'x' + str(u)
            y = 'y' + str(v)
            V0 = V0 | {x}
            V1 = V1 | {y}
            E = E | {(x, y)}
    return [V0, V1, E]

def completebigraphlist(m,n):   #生成完全偶图列表
    Vx = set(range(m))
    Vy = set(range(n))
    V0 = set({})
    V1 = set({})
    E = list({})
    for u in Vx:
        for v in Vy:
            x = 'x' + str(u)
            y = 'y' + str(v)
            V0 = V0 | {x}
            V1 = V1 | {y}
            E = E + [[x, y]]
    return [V0, V1, E]